package com.demo.java.OD401_450.OD441;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【文件缓存系统(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146326072
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {
            // 读取输入的最大容量和操作数
            int capacity = in.nextInt();
            int num = in.nextInt();
            Map<String, FileTest> fileMap = new HashMap<>(); // 存储文件信息
            int totalSize = 0; // 当前文件总大小
            int index = 1; // 访问顺序
            in.nextLine(); // 读取换行符
            for (int i = 0; i < num; i++) {
                String cmd = in.nextLine(); // 读取每一条操作
                String[] arr = cmd.split(" "); // 将操作按空格分割
                if ("get".equals(arr[0])) { // 处理get操作
                    FileTest file = fileMap.get(arr[1]);
                    if (file != null) {
                        file.times++; // 更新访问次数
                        file.index = index++; // 更新访问顺序
                    }
                } else { // 处理put操作
                    if (!fileMap.containsKey(arr[1])) { // 文件不存在时
                        int size = Integer.parseInt(arr[2]);
                        if (totalSize + size <= capacity) { // 如果有足够空间，直接添加文件
                            totalSize += size;
                            fileMap.put(arr[1], new FileTest(arr[1], size, index++));
                        } else { // 没有足够空间时，移除文件
                            totalSize = remove(fileMap, capacity, totalSize, size);
                            if (totalSize + size <= capacity) {
                                totalSize += size;
                                fileMap.put(arr[1], new FileTest(arr[1], size, index++));
                            }
                        }
                    }
                }
            }
            // 输出当前文件存储系统中的所有文件，按字母顺序排列
            if (fileMap.isEmpty()) {
                System.out.println("NONE");
            } else {
                System.out.println(fileMap.keySet().stream().sorted().collect(Collectors.joining(",")));
            }
        }
    }

    // 移除文件直到腾出足够空间
    public static int remove(Map<String, FileTest> fileMap, int capacity, int currentSize, int size) {
        List<FileTest> list = fileMap.values().stream()
                .sorted(Comparator.comparing(FileTest::getTimes).thenComparing(FileTest::getIndex))
                .collect(Collectors.toList());
        int result = currentSize;
        // 删除文件直到腾出空间
        for (FileTest fileTest : list) {
            if (result + size >= capacity) {
                fileMap.remove(fileTest.fileName);
                result -= fileTest.size;
            } else {
                break;
            }
        }
        return result;
    }

    // 文件类，存储文件的大小、访问次数和索引
    static class FileTest {
        String fileName;
        int size;
        int times;
        int index;

        public FileTest(String fileName, int size, int index) {
            this.fileName = fileName;
            this.size = size;
            this.index = index;
        }

        public int getIndex() {
            return index;
        }

        public int getTimes() {
            return times;
        }
    }
}
